#ifndef AVL_TREE_H
#define AVL_TREE_H

#include "BinaryTree.h"

class AvlTree : public BinaryTree
{
public:
	AvlTree()
		: BinaryTree()
	{
	}

private:
	void rotate_right(Node* &node)
	{
		Node *temp = node->left;
		node->left = temp->right;
		temp->right = node;
		node = temp;
	}

	void rotate_right_left(Node* &node)
    {
        rotate_right(node->right);
        rotate_left(node);
    }
        
    void rotate_left(Node* &node)
    {
        Node *temp = node->right;
        node->right = temp->left;
        temp->left = node;
        node = temp;
    }
        
    void rotate_left_right(Node* &node)
    {
        rotate_left(node->left);
        rotate_right(node);
    }

    virtual void insert(Node* &node, double d) 
	{
		if (!node) node = new Node(d);

        if (d < node->data) 
		{
            insert(node->left, d);
                
            if (height(node->left) - height(node->right) == 2) 
                (d < node->left->data) ? rotate_right(node) : rotate_left_right(node);					
        }

        else if (d > node->data) 
		{
            insert(node->right, d);

            if (height(node->right) - height(node->left) == 2)
                (d > node->right->data) ? rotate_left(node) : rotate_right_left(node);
        }
    }
};
#endif